package recursion;

import java.util.Arrays;

/**
 * 迷宫问题
 * 这里存在一个最短路径的问题（目前解决方案就是跑每一个策略）
 * @Auther Jun jie Yi
 * @Date 11:07 2021/7/11
 */
public class Maze {
    public static void main(String[] args) {
        //先创建一个二维数组模拟迷宫
        //地图
        int[][] map = new int[8][7];
        //上下全部置为1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //上下全部置为1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        //挡板设为1
        map[3][1] = 1;
        map[3][2] = 1;
        //再加两个挡板将路堵死
        //map[1][2] = 1;
        //map[2][2] = 1;

        Arrays.stream(map).forEach(e -> {
            Arrays.stream(e).forEach(e1 -> System.out.print(e1 + " "));
            System.out.println();
        });

        //使用递归回溯给小球找路
        //setWay(map, 1, 1);
        setWay1(map, 1, 1);

        //使用1表示墙，不能去动
        System.out.println("-----------------------------");
        Arrays.stream(map).forEach(e -> {
            Arrays.stream(e).forEach(e1 -> System.out.print(e1 + " "));
            System.out.println();
        });
    }

    /**
     * 1. map 表示地图
     * 2.i，j 表示地图从哪个位置开始出发
     * 3.如果小球能到 map[6][5] 位置，说明通路能找到
     * 4.约定：当 map[i][j] 为 0 表示该点没有走过 当为 1 表示墙 2 表示通路可以走 3.表示该点已经走过，但是走不通
     * 5.在走迷宫时，需要确定一个策略（方法）下 -> 右 -> 上 -> 左，如果该点走不通，再回溯
     */
    /**
     *
     * @param map 表示地图
     * @param i 从哪个位置开始找
     * @param j 从哪个位置开始找
     * @return 如果找到通路就返回 true，否则就返回 false
     */
    public static boolean setWay(int[][] map, int i, int j) {
        if(map[6][5] == 2) {//通路已经找到
            return true;
        } else {
            if(map[i][j] == 0) {//如果当前这个路径没有走过
                //按照策略 下 -> 右 -> 上 -> 左 走
                map[i][j] = 2; //假定该点可以走通
                if(setWay(map, i + 1, j)) {//向下走
                    return true;
                } else if(setWay(map, i , j + 1)) {//向右走
                    return true;
                } else if(setWay(map, i - 1 , j)) {//向上走
                    return true;
                } else if(setWay(map, i , j - 1)) {//向左走
                    return true;
                } else {
                    map[i][j] = 3;//说明该点走不通，是死路
                }
            } else {//如果 map[i][j] != 0，可能是 1,2,3
                return false;
            }
        }
        return false;
    }
    //修改策略为 上 -> 下 -> 左 -> 右
    public static boolean setWay1(int[][] map, int i, int j) {
        if(map[6][5] == 2) {//通路已经找到
            return true;
        } else {
            if(map[i][j] == 0) {//如果当前这个路径没有走过
                //按照策略 下 -> 右 -> 上 -> 左 走
                map[i][j] = 2; //假定该点可以走通
                if(setWay(map, i, j - 1)) {//向上走
                    return true;
                } else if(setWay(map, i , j + 1)) {//向下走
                    return true;
                } else if(setWay(map, i - 1 , j)) {//向左走
                    return true;
                } else if(setWay(map, i + 1 , j)) {//向右走
                    return true;
                } else {
                    map[i][j] = 3;//说明该点走不通，是死路
                }
            } else {//如果 map[i][j] != 0，可能是 1,2,3
                return false;
            }
        }
        return false;
    }
}
